#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>
using namespace std;

struct Node
{
    string val;
    int count;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(const string& v, int c) :val(v), count(c) {}
};
int H(Node* root)
{
    if (!root) return 0;
    int l = H(root->left), r = H(root->right);
    return 1 + max(l, r);
}

struct Compare
{
    bool operator()(Node* a, Node* b) {
        if (a->count != b->count)
            return a->count > b->count;
        return H(a) > H(b);
    }
};

map<string, string> codes;
void getCode(Node* root, string code = "")
{
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->val] = code;
        return;
    }
    getCode(root->left, code + "0");
    getCode(root->right, code + "1");
}

void c(Node* h)
{
    queue<Node*> q;
    q.push(h);
    while (q.size()) {
        auto cur = q.front(); q.pop();
        if (!cur) continue;
        auto l = cur->left, r = cur->right;
        if (!l && !r) cout << cur->val;
        cout << "(" << cur->count << ") ";
        q.push(l); q.push(r);
    }
}
void prev(Node* h, Node* gp)
{
    if (!h) return;
    if (!h->left && !h->right) cout << h->val;
    cout << "(" << h->count << ") ";
    prev(h->left, gp);
    prev(h->right, gp);
}
void in(Node* h)
{
    if (!h) return;
    in(h->left);
    if (!h->left && !h->right) cout << h->val;
    cout << "(" << h->count << ") ";
    in(h->right);
}
void post(Node* h, Node* gp)
{
    if (!h) return;
    post(h->left, gp);
    post(h->right, gp);
    if (!h->left && !h->right) cout << h->val;
    cout << "(" << h->count << ") ";
}

int main()
{
    int n; cin >> n;
    vector<string> val(n);
    vector<int> count(n);
    for (int i = 0; i < n; i++) cin >> val[i];
    for (int i = 0; i < n; i++) cin >> count[i];

    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (int i = 0; i < n; i++) pq.push(new Node(val[i], count[i]));

    while (pq.size() > 1) {
        Node* l = pq.top(); pq.pop();
        Node* r = pq.top(); pq.pop();
        Node* p = new Node("", l->count + r->count);
        p->left = l;
        p->right = r;
        if (l->count > r->count || (l->count == r->count && H(l) > H(r)))
            swap(p->left, p->right);
        pq.push(p);
    }
    Node* root = pq.top();

    c(root); cout << endl;
    prev(root, root); cout << endl;
    in(root); cout << endl;
    post(root, root); cout << endl;
    getCode(root);
    for (int i = 0; i < n; i++) cout << endl << val[i] << ":" << codes[val[i]];
    return 0;
}
//
//测试用例 7068结果为 TLE:运行超时
//5
//d i a n w
//7 5 2 4 9
//
//测试用例 7069结果为 TLE:运行超时
//6
//d i a n w u
//7 5 2 4 9 3
//
//测试用例 7404结果为 TLE:运行超时
//8
//d i a n q u e x
//5 29 7 8 14 23 3 11
//
//测试用例 7405结果为 TLE:运行超时
//7
//a b c d e f g
//3 12 7 4 2 8 11
